package PriorityQueue;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-26
 * Time: 8:45
 */

/**
 * 面试题 ：最小K个数：
 *
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 *
 * 示例：
 *
 * 输入： arr = [1,3,5,7,2,4,6,8], k = 4
 * 输出： [1,2,3,4]
 * 提示：
 *
 * 0 <= len(arr) <= 100000
 * 0 <= k <= min(100000, len(arr))
 */

public class PriorityQueueExercise1 {

    /**
     * 解法一，把数组放入小根堆里，再拿出来K个
     * //时间复杂度 0( (N+k)*logN )
     * @param arr
     * @param k
     * @return
     */

    public int[] smallestK (int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        //时间复杂度 0(N*logN)
        for (int i = 0; i < arr.length; i++) {
            //默认是小根堆
            priorityQueue.offer(arr[i]);
        }

        //时间复杂度 0(K*logN)
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }





    /**
     * 解法二：把 N个元素的数组，前 K个变成大根堆，再与 N-K个比较，
     * 如果第 N-K个，比堆顶元素小，就把堆顶元素删除，把这个元素放入堆中。
     *
     * //时间复杂度 0( K*logK + (N-K)*logK == N*logK)这里的K可能很小，所以该算法比较好
     */


    //构建大根堆
    class IntCmp implements Comparator<Integer>{

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    }


    public int[] smallestK2(int[] arr, int k) {

        int[] ret = new int[k];
        //注意K的范围
        if(arr == null || k == 0) {
            return ret;
        }

        //前 K个变成大根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k,new IntCmp());
        //时间复杂度 O（K*logK）
        for (int i = 0; i < k; i++) {
            //现在是大根堆
            priorityQueue.offer(arr[i]);
        }



        //第 N-K个元素从，K下标开始
        //时间复杂度：(N-K)*logK
        for (int i = k; i < arr.length; i++) {
            //peek一下堆顶元素，与开始第K个一直比较
            int peekVal = priorityQueue.peek();
            if (arr[i] < peekVal) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
}
